package com.desheng.bigdata.ds.stack;

import java.util.Iterator;

/**
 * @Description 通过链表来模拟栈结构（FIFO）
 * @Author deshenglijun
 * @Date 2020/5/13 21:35
 * @Version 1.0
 */
public class Stack<E> implements Iterable<E> {

    private class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }
    //栈的深度
    private int size;
    //栈中空节点，用来连接其他元素
    private Node<E> head;

    /*
     * 初始化一个空栈
     */
    public Stack() {
        this.head = new Node<E>(null, null);
        this.size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void push(E e) {
        Node<E> oldFirst = head.next;
        Node<E> newFirst = new Node<>(e, oldFirst);
        head.next = newFirst;
        size++;
    }

    public E pop() {
        if(size == 0) {
            return null;
        }
        Node<E> oldFirst = head.next;
        head.next = oldFirst.next;
        size--;
        return oldFirst.data;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>(){
            Node<E> node = head;
            @Override
            public boolean hasNext() {
                return node.next != null;
            }

            @Override
            public E next() {
                node = node.next;
                return node.data;
            }
        };
    }
}
